package LeetCode.month04.day116;

/**
 * @author 16778
 * @date 2025/11/26 8:13
 * @description
 */
public class No2435 {
    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][][] memo = new int[m][n][k];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                for(int l=0;l<k;l++){
                    memo[i][j][l] = -1;
                }
            }
        }
        return dfs(grid,0,0,k,0,memo);
    }

    public int dfs(int[][] grid,int row,int col,int k,int sum,int[][][]memo){
        if(row>=grid.length||col>=grid[0].length){
            return 0;
        }
        sum = (sum+grid[row][col])%k;
        if(memo[row][col][sum]!=-1){
            return memo[row][col][sum];
        }
        if(row==grid.length-1&&col==grid[0].length-1){
            return sum==0?1:0;
        }
        int res = (dfs(grid,row+1,col,k,sum,memo)+dfs(grid,row,col+1,k,sum,memo))%1000000007;
        return memo[row][col][sum] = res;
    }
}
